Trading precision for performance is a recognized opportunity for optimization of computing systems. For example, in the reconfigurable computing field, techniques were developed to optimize bit width to save gates in a field programmable gate array (FPGA) computing applications. These techniques, however, are generally directed to finding the minimum number of bits that could fit the range of values for variables rather than approximating the computations of functions/procedures.
Approximation based optimization (ABO) is generally directed to optimizations that can explore precision-performance tradeoffs by using approximations of computationally intensive functions/procedures. ABO can be considered to be a generalization of the classical compiler optimization called “strength reduction” which, in particular, can be beneficial in loop codes, e.g., by transforming expensive multiply operations into recurrences of additions. Generally in ABO, implementation of expensive computations such as transcendental function evaluation is replaced with approximations that take much less work to compute. As such, the overall execution of a program in which the execution of one or more functions/procedures is replaced with corresponding approximation(s) can be improved, e.g., in terms of execution time, number of computations, etc. ABO can be useful in many computationally intensive applications including signal processing associated with synthetic aperture radars (SARs), image processing, processing of cellular communication signals, speech signals, etc.
ABO in Compute-Bound Programs
Many compute-bound (also called computationally intensive) programs spend a significant portion of their cycles in standard numerical library functions (e.g., square root, trigonometric, etc.) applied to values that change at every loop iteration. If the function arguments are contiguous in the iteration domain, and if the variation of the arguments is small enough from one iteration to the next, it is possible to replace a series of expensive-but-precise computations based on numerical library calls with one expensive-but-precise computation followed by a series of inexpensive-but-imprecise computations of the neighboring values. At some point, the accumulated error from the imprecise computations becomes unacceptable, in which case a precise computation is needed.
Such a replacement of precise functions/procedures with relatively imprecise functions/procedures in compute-bound programs in general, however, can introduce computation errors which, in some instances, can be unacceptable, i.e., these errors can cause the program to produce erroneous results. Moreover, in some instances an ad hoc replacement of an exact procedure/function with a corresponding approximation, such as a replacement specified by a programmer, can adversely affect optimization of the program. For example, the use of an approximation can affect loop tiling, which can limit the benefits of optimizing memory locality, data transfers between main memory and cache memory, and/or parallelized execution of the program.